package array;
import java.util.HashMap;
import java.util.Map;


// 移除一段最短连续子数组_使得剩下的数字和为k的整数倍

//同余定理  相减能被k整除 ->  total % k = delete % k  -> delete % k = 常数mod  -> (pre[j] -pre[i-1]) % k = mod -> 
//pre[j] % k  - mod = pre[i-1] % k  ->( pre[j] - mod)%k = pre[i-1] % k

//因此  可以先求总和  然后依次保存  (pre[i-1]% k , j) （用map） 然后对每个j  求出(pre[j] - mod) % k值相等的前一个 i - 1的值  找最小的长度即可
public class 删除最短长度使得数组中余下数字能被k整除{
            public int solve(int[] nums, int k) {
                int targetMod = 0,prefixSum = 0, res = nums.length;
                for(int num : nums) {
                    targetMod += num;
                }
                targetMod %= k;
                Map<Integer, Integer> map = new HashMap<>();
                map.put(0, -1); // mod余0 从0开始  加上第0位 放 -1
                for(int i = 0; i < nums.length; i ++) {
                    prefixSum += nums[i];
                    int mod = Math.floorMod(prefixSum - targetMod, k);
                    if(map.containsKey(mod)) {
                        res = Math.min(i - map.get(mod), res);
                    }

                    // i - 1用于在减去求长度的时候加上第i位
                    map.put(Math.floorMod(prefixSum, k), i - 1);
                }

                return res == nums.length ? -1 : res;
            }
        }
